1. Field of the Invention
This invention relates to a normalization processing method used on a coding algorithm of MQ-CODER, which is an arithmetic coding system, and an arithmetic coding/decoding apparatus of the MQ-CODER system.
This application claims priority of Japanese Patent Application No.2002-054574, filed on Feb. 28, 2002, the entirety of which is incorporated by reference herein.
2. Description of the Related Art
As an arithmetic coding system, a coding system called MQ-CODER is known. This MQ-CODER is employed as an arithmetic coding system of JPEG2000 (ISO/IEC JTC 1/SC 29/WG1) or the like. This MQ-CODER coding/decoding algorithm is described in detail, for example, in the following literature:
xe2x80x9cNext-Generation Image Coding System JPEG2000,xe2x80x9d (Triceps) issued on Feb. 13, 2001; and
xe2x80x9cJPEG2000 Part 1 Final Committee Draft Version 1.0,xe2x80x9d (SO/IEC JTC 1/SC 29/WG1, JPEG2000 Editor Martin Boliek, Co-editors, Charilaos Christopoulos and Eric Majani) issued on Apr. 11, 2000.
With this MQ-CODER coding/decoding algorithm, renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) are carried out. Renormalization processing in coding (RENORME) is used for the processing on the final stage of LPS coding (CODELPS) and MPS coding (CODEMPS). LPS means less predominant symbol and MPS means more predominant symbol. Renormalization processing in decoding (RENORMD) is used for the processing on the final stage of decoding processing (DECODE). In decoding processing (DECODE), the processing may end without carrying out this renormalization processing in decoding (RENORMD) depending on the results of segmentation and selection processing, which is carried out before renormalization processing in decoding (RENORMD). Also in some cases in coding processing (ENCODE), the processing may end without carrying out renormalization processing in coding (RENORME).
Hereinafter, renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) will be described. The data contents of A, C, BP, B, B1 and CT referred to in renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) are the same as the data contents described in the foregoing literature. The following are the details of the data contents.
A is a value stored in an augend register. It is binary data with a 16-bit length.
C is a value stored in a code register. It is binary data with a 28-bit length.
BP is a pointer of a byte buffer.
B is data of a position indicated by BP of a byte buffer. It is binary data with an 8-bit length.
B1 is data of a position indicated by BP+1 of a byte buffer. It is binary data with an 8-bit length.
CT is a value of a free byte counter for counting free bits. It is binary data with a 4-bit length.
An arithmetic formula xe2x80x9cX greater than  greater than Yxe2x80x9d means that right bit shift of binary data X by Y bits is carried out. An arithmetic formula xe2x80x9cX less than  less than Yxe2x80x9d means that left bit shift of binary data X by Y bits is carried out. xe2x80x9c0xXX . . . Xxe2x80x9d means binary data of hexadecimal expression. X represents hexadecimal numbers 0 to F.
FIG. 3 shows a processing flow of renormalization processing in coding (RENORME).
In renormalization processing in coding (RENORME), first, left bit shift of A and C by 1 bit is carried out and 1 is subtracted from CT (step S11).
Then, whether CT is 0 or not is judged (step S12). If CT is 0, subroutine processing of byteout processing (BYTEOUT) of step S13 is carried out. When this subroutine of byteout processing (BYTEOUT) ends, the processing goes to step S14. If CT is not 0, the processing goes directly to step S14.
Next, arithmetic operation of (Aand0x8000) is carried out and whether the result of this arithmetic operation is 0 or not is judged (step S14). That is, at step S14, whether MSB of A stored in an augend register is 1 or not is judged.
If the result of arithmetic operation at step S14 is 0, the processing is repeated again from step S11. If the result of arithmetic operation is not 0, this flow ends.
In short, in this renormalization processing in coding (RENORME), left bit shift precessing of the value of A stored in the augend register is carried out until the value of A reaches 0x8000 or more.
FIG. 4 shows a processing flow of byteout processing (BYTEOUT) at step S13 of the above-described renormalization processing in coding (RENORME).
In byteout processing (BYTEOUT), first, whether B is 0xFF or not is judged (step S21). If B is 0xFF, the processing goes to step S27. If B is not 0xFF, the processing goes to the next step S22.
Next, whether C is smaller than 0x8000000 or not is judged (step S22). If C is smaller than 0x8000000, the processing goes to step S26. If C is equal to or larger than 0x8000000, the processing goes to the next step S23.
Next, 1 is added to B (step S23).
Next, whether B is 0xFF or not is judged (step S24). If B is 0xFF, the processing goes to the next step S25. If B is not 0xFF, the processing goes to step S26.
Next, arithmetic operation of (Cand0x7FFFFFF) is carried out and the result of this arithmetic operation is substituted in C (step S26). Then, the processing goes to step S27.
At step S26, 1 is added to BP and a value obtained by performing right bit shift of C by 19 bits is substituted in B. Then, arithmetic operation of (Cand0x7FFFF) is carried out and its value is substituted in C. Then, 8 is substituted in CT.
At step S27, 1 is added to BP and a value obtained by performing right bit shift of C by 20 bits is substituted in B. Then, arithmetic operation of (Cand07FFFFF) is carried out and its value is substituted in C. Then, 7 is substituted in CT.
In byteout processing (BYTEOUT), as the processing of step S26 or step S27 ends, the subroutine processing ends.
FIG. 5 shows a processing flow of renormalization processing in decoding (RENORMD).
In renormalization processing in decoding (RENORMD), first, whether CT is 0 or not is judged (step S31). If CT is 0, the processing goes to the subroutine of bytein processing (BYTEIN) of step S32. As this subroutine of bytein processing (BYTEIN) ends, the processing goes to step S33. If CT is not 0, the processing goes directly to step S33.
Next, left bit shift of A and C by 1 bit is carried out and 1 is subtracted from CT (step S33).
Then, arithmetic operation of (Aand0x8000) is carried out and whether the result of this arithmetic operation is 0 or not is judged (step S34). That is, at step S34, whether MSB of A stored in an augend register is 1 or not is judged.
If the result of arithmetic operation at step S34 is 0, the processing is repeated again from step S31. If the result of arithmetic operation is not 0, this flow ends.
In short, in this renormalization processing in decoding (RENORMD), left bit shift precessing of the value of A stored in the augend register is carried out until the value of A reaches 0x8000 or more.
FIG. 6 shows a processing flow of bytein processing (BYTEIN) at step S32 of the above-described renormalization processing in decoding (RENORMD).
In bytein processing (BYTEIN), first, whether B is 0xFF or not is judged (step S41). If B is 0xFF, the processing goes to the next step S42. If B is not 0xFF, the processing goes to step S45.
Next, whether B1 is larger than 0x8F or not is judged (step S42). If B1 is larger than 0x8F, the processing goes to step S43. If B1 is equal to or smaller than 0x8F, the processing goes to the next step S44.
At step S43, 1 is added to BP, and C is added to a value obtained by performing right left bit shift of B by 9 bits. The result of this addition is substituted in C. Then, 7 is substituted in CT.
At step S44, 0xFF00 is added to C and the result of this addition is substituted in C. Then, 8 is substituted in CT.
At step S45, 1 is added to BP, and C is added to a value obtained by performing right left bit shift of B by 8 bits. The result of this addition is substituted in C. Then, 8 is substituted in CT.
In bytein processing (BYTEIN), as the processing of step S43, step S44 or step S45 ends, the subroutine processing ends.
Meanwhile, in the above-described renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD), a loop for performing left bit shift of A by 1 bit is formed, and the processing goes out of the loop when the value of A reaches 0x8000 or more. Since loop processing is carried out for each bit shift, a larger quantity of bit shift takes a longer processing time and the time for processing a set of data (symbol, context) varies. Moreover, as different processing modules must be used for coding and decoding, the circuit scale based on software and hardware is increased.
In view of the foregoing status of the art, it is an object of the present invention to provide an arithmetic coding/decoding apparatus of the MQ-CODER system and a renormalization method that require a short processing time and a reduced circuit scale.
An arithmetic coding/decoding apparatus of the MQ-CODER system according to the present invention comprises renormalization means for performing renormalization processing in coding and renormalization processing is decoding based on the MQ-CODER system with reference to the values of an augend register A, a code register C and a free byte counter CT.
The renormalization means comprises: a number-of-shift calculation step of calculating the number of times of shift in the case where left shift of the value of the augend register A by 1 bit is performed until MSB reaches 1, and outputting the number of times as the number of shifts SHIFT_A; a first left bit shift step of performing left shift of the value of the augend register A by bits of the value indicated by the number of shifts SHIFT_A; a subtraction step of subtracting the value of the free byte counter CT from the number of shifts SHIFT_A; a byteout/bytein step of performing byteout processing in the case where the result of subtraction of the subtraction step is not negative at the time of coding, and performing bytein processing in the case where the result of subtraction of the subtraction step is not negative at the time of decoding and in the case where the value of the free byte counter CT is not 0 and the value of the free byte counter CT and the number of shifts SHIFT_A are the same value and normalization is carried out, at the time of decoding; a second left bit shift step of performing left shift of the code register C by bits of the value indicated by the free byte counter CT in the case where byteout processing or bytein processing is performed at the byteout/bytein step, and performing left shift of the code register C by bits of the value indicated by the number of shifts SHIFT_A in the case where byteout processing or bytein processing is not performed at the byteout/bytein step; a CT value selection step of setting the absolute value of the result of subtraction of the subtraction step as the value of the free byte counter CT in the case where byteout processing or bytein processing is not performed at the byteout/bytein step, and setting the value of the free byte counter CT at 0 in the case where byteout processing or bytein processing is performed at the byteout/bytein step; and a number-of-remaining-loop selection step of setting the value of the number of shifts SHIFT_A at 0 in the case where byteout processing or bytein processing is not performed at the byteout/bytein step, and setting the absolute value of the result of subtraction of the subtraction step as the number of shifts SHIFT_A in the case where byteout processing or bytein processing is performed at the byteout/bytein step. The renormalization means ends the processing if the value of the number of shifts SHIFT_A outputted from the number-of-remaining-loop selection step is 0, and repeats the processing from the subtraction step if the value of the number of shifts SHIFT_A is not 0.
In this arithmetic coding/decoding apparatus of the MQ-CODER system, the value of the augend register A is calculated without performing any loop processing. In this arithmetic coding/decoding apparatus of the MQ-CODER system, whether byteout processing or bytein processing occurs or not is judged on the basis of the positive or negative sign of (number of shifts SHIFT_A minus free byte counter CT) and the value of the free byte counter CT. If byteout processing or bytein processing occurs, the values of the code register C and the free byte counter CT before this byteout processing or bytein processing are calculated. If byteout processing or bytein processing does not occur, the values of the code register C and the free byte counter CT up to the end of normalization processing are calculated. Then, if the value of (number of shifts SHIFT_A minus free byte counter CT) is a positive value after byteout processing or bytein processing, the result of this subtraction is substituted in the number of shifts SHIFT_A and renormalization processing is performed again.
A renormalization method according to the present invention is a renormalization method used in arithmetic coding/decoding processing of the MQ-CODER system for performing renormalization processing in coding and renormalization processing in decoding with reference to the values of au augend register A, a code register C and a free byte counter CT.
This renormalization method comprises: a number-of-shift calculation step of calculating the number of times of shift in the case where left shift of the value of the augend register A by 1 bit is performed until MSB reaches 1, and outputting the number of times as the number of shifts SHIFT_A; a first left bit shift step of performing left shift of the value of the augend register A by bits of the value indicated by the number of shifts SHIFT_A; a subtraction step of subtracting the value of the free byte counter CT from the number of shifts SHIFT_A; a byteout/bytein step of performing byteout processing in the case where the result of subtraction of the subtraction step is not negative at the time of coding, and performing bytein processing in the case where the result of subtraction of the subtraction step is not negative at the time of decoding and in the case where the value of the free byte counter CT is not 0 and the value of the free byte counter CT and the number of shifts SHIFT_A are the same value and normalization is carried out, at the time of decoding; a second left bit shift step of performing left shift of the code register C by bits of the value indicated by the free byte counter CT in the case where byteout processing or bytein processing is performed at the byteout/bytein step, and performing left shift of the code register C by bits of the value indicated by the number of shifts SHIFT_-A in the case where byteout processing or bytein processing is not performed at the byteout/bytein step; a CT value selection step of setting the absolute value of the result of subtraction of the subtraction step as the value of the free byte counter CT in the case where byteout processing or bytein processing is not performed at the byteout/bytein step, and setting the value of the free byte counter CT at 0 in the case where byteout processing or bytein processing is performed at the byteout/bytein step; and a number-of-remaining-loop selection step of setting the value of the number of shifts SHIFT_A at 0 in the case where byteout processing or bytein processing is not performed at the byteout/bytein step, and setting the absolute value of the result of subtraction of the subtraction step as the number of shifts SHIFT_A in the case where byteout processing or bytein processing is performed at the byteout/bytein step. The processing ends if the value of the number of shifts SHIFT_A outputted from the number-of-remaining-loop selection step is 0, and the processing is repeated from the subtraction step if the value of the number of shifts SHIFT_A is not 0.
In this renormalization method, the value of the augend register A is calculated without performing any loop processing. In this renormalization method, whether byteout processing or bytein processing occurs or not is judged on the basis of the positive or negative sign of (number of shifts SHIFT_A minus flee byte counter CT) and the value of the free byte counter CT. If byteout processing or bytein processing occurs, the values of the code register C and the free byte counter CT before this byteout processing or bytein processing are calculated. If byteout processing or bytein processing does not occur, the values of the code register C and the free byte counter CT up to the end of normalization processing are calculated. Then, if the value of (number of shifts SHIFT_A minus free byte counter CT) is a positive value after byteout processing or bytein processing, the result of this subtraction is substituted in the number of shifts SHIFT_A and renormalization processing is performed again.
In the arithmetic coding/decoding apparatus of the MQ-CODER system and the renormalization method according to the present invention, the value of the augend register A is calculated without performing any loop processing. According to the present invention, whether byteout processing or bytein processing occurs or not is judged on the basis of the positive or negative sign of (number of shifts SHIFT_A minus free byte counter CT) and the value of the free byte counter CT. If byteout processing or bytein processing occurs, the values of the code register C and the free byte counter CT before this byteout processing or bytein processing are calculated. If byteout processing or bytein processing does not occur, the values of the code register C and the free byte counter CT up to the end of normalization processing are calculated. Then, if the value of (number of shifts SHIFT_A minus free byte counter CT) is a positive value after byteout processing or bytein processing, the result of this subtraction is substituted in the number of shifts SHIFT_A and renormalization processing is performed again.
Thus, according to the present invention, the processing time can be reduced and the circuit scale can be reduced.
Moreover, according to the present invention, the value of the augend register A is calculated without performing any loop processing, and if byteout processing or bytein processing occurs, the values of the code register C and the free byte counter CT before this byteout processing or bytein processing are calculated, and if byteout processing or bytein processing does not occur, the values of the code register C and the free byte counter CT up to the end of normalization processing are calculated. Therefore, renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) can be performed in a common circuit.
Furthermore, according to the present invention, if byteout processing or bytein processing occurs, the processing before this byteout processing or bytein processing is performed without any loop operation, and if byteout processing or bytein processing does not occur, the processing up to the end of normalization processing is performed without any loop operation. Therefore, the time for processing each data can be made even.